{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Length of Repeated Subarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #dynamic-programming #sliding-window #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #动态规划 #滑动窗口 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长重复子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给两个整数数组&nbsp;<code>nums1</code>&nbsp;和&nbsp;<code>nums2</code>&nbsp;，返回 <em>两个数组中 <strong>公共的</strong> 、长度最长的子数组的长度&nbsp;</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>长度最长的公共子数组是 [3,2,1] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums1.length, nums2.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-length-of-repeated-subarray](https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-length-of-repeated-subarray](https://leetcode.cn/problems/maximum-length-of-repeated-subarray/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,2,1]\\n[3,2,1,4,7]', '[0,0,0,0,0]\\n[0,0,0,0,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        '''\n",
    "        Brute force: list out all the subarray for these two arrays \n",
    "        and find out the same subarrays appearing in both of these two arrays\n",
    "        \n",
    "        Listing out all subarrays for an array takes O(n**2) in time and O(n**2) in space as well\n",
    "        \n",
    "       1/2 3 2 1 4 7\n",
    "        1  0 0 1 0 0\n",
    "        2  0 1 0 0 0 \n",
    "        3  1 0 0 0 0 \n",
    "        2  0 2 0 0 0 \n",
    "        1  0 0 3 0 0 \n",
    "        i represents the index in arr1, j represents index in array2\n",
    "        \n",
    "        dp[i][j] = arr[i-1][j-1] + 1 if arr1[i] == arr2[j] else arr[i][j-1]\n",
    "        '''\n",
    "        dp = [[0 for _ in range(len(nums2)+1)] for _ in range(len(nums1)+1) ]\n",
    "        largest = 0\n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(1, len(dp[0])):\n",
    "                if nums1[i-1] == nums2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+1\n",
    "            largest = max(largest, max(dp[i]))  \n",
    "        return largest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A, B):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type B: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        la,lb=len(A),len(B)\n",
    "        res=0\n",
    "    \n",
    "        for i in range(la):\n",
    "            temp=0\n",
    "            for j in range(lb):\n",
    "                if i+j==la:\n",
    "                    break\n",
    "                if A[i+j]==B[j]:\n",
    "                    temp+=1\n",
    "                    res=max(temp,res)\n",
    "                else:\n",
    "                    temp=0\n",
    "                    \n",
    "        for i in range(lb):\n",
    "            temp=0\n",
    "            for j in range(la):\n",
    "                if i+j==lb:\n",
    "                    break\n",
    "                if B[i+j]==A[j]:\n",
    "                    temp+=1\n",
    "                    res=max(temp,res)\n",
    "                else:\n",
    "                    temp=0\n",
    "                    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A, B):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type B: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(A) > len(B): \n",
    "            return findLength(B, A)\n",
    "\n",
    "        def check(length):\n",
    "            lookup = set(A[i:i+length] for i in range(len(A)-length+1))\n",
    "            return any(B[j:j+length] in lookup for j in range(len(B)-length+1))\n",
    "\n",
    "        A = ''.join(map(chr, A))\n",
    "        B = ''.join(map(chr, B))\n",
    "        \n",
    "        left, right = 0, len(B)+1\n",
    "        while left < right:\n",
    "            mid =  (right+left)//2\n",
    "            if not check(mid):  # find the min idx such that check(idx) == false\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "        size_a=len(A)\n",
    "        size_b=len(B)\n",
    "        count=0\n",
    "        for i in range(size_a):\n",
    "            j=0\n",
    "            t=0\n",
    "            while i<size_a and j<size_b:\n",
    "                if A[i]==B[j]:\n",
    "                    t+=1\n",
    "                else:\n",
    "                    t=0\n",
    "                i+=1\n",
    "                j+=1\n",
    "                if t>count:\n",
    "                    count=t\n",
    "        for i in range(size_b):\n",
    "            j=0\n",
    "            t=0\n",
    "            while i<size_b and j<size_a:\n",
    "                if A[j]==B[i]:\n",
    "                    t+=1\n",
    "                else:\n",
    "                    t=0\n",
    "                i+=1\n",
    "                j+=1\n",
    "                if t>count:\n",
    "                    count=t\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "        longest = []\n",
    "        res = 0\n",
    "        bb = \"\".join([\"'%s'\" % b for b in B])\n",
    "        for i in range(len(A)):\n",
    "            while len(A) - i > res:\n",
    "                \n",
    "                longest = A[i:i+res+1]\n",
    "                if bb.find(\"\".join([\"'%s'\" % l for l in longest])) >= 0:\n",
    "                    res += 1\n",
    "                else:\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "        def maxLength(addA: int, addB: int, length: int) -> int:\n",
    "            ret = k = 0\n",
    "            for i in range(length):\n",
    "                if A[addA + i] == B[addB + i]:\n",
    "                    k += 1\n",
    "                    ret = max(ret, k)\n",
    "                else:\n",
    "                    k = 0\n",
    "            return ret\n",
    "        \n",
    "        n, m = len(A), len(B)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            length = min(m, n - i)\n",
    "            ret = max(ret, maxLength(i, 0, length))\n",
    "        for i in range(m):\n",
    "            length = min(n, m - i)\n",
    "            ret = max(ret, maxLength(0, i, length))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "        def maxLength(addA: int, addB: int, length: int) -> int:\n",
    "            ret = k = 0\n",
    "            for i in range(length):\n",
    "                if A[addA + i] == B[addB + i]:\n",
    "                    k += 1\n",
    "                    ret = max(ret, k)\n",
    "                else:\n",
    "                    k = 0\n",
    "            return ret\n",
    "        \n",
    "        n, m = len(A), len(B)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            length = min(m, n - i)\n",
    "            ret = max(ret, maxLength(i, 0, length))\n",
    "            if length == ret:\n",
    "                break\n",
    "        for i in range(m):\n",
    "            length = min(n, m - i)\n",
    "            ret = max(ret, maxLength(0, i, length))\n",
    "            if length == ret:\n",
    "                break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "        def check(v):\n",
    "            hashmap = set()\n",
    "            for i in range(len(A) - v + 1):\n",
    "                hashmap.add(\"\".join(str(a) for a in A[i:i + v]))\n",
    "            for i in range(len(B) - v + 1):\n",
    "                if \"\".join(str(b) for b in B[i:i + v]) in hashmap:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        ans = 0\n",
    "        left, right = 0, min(len(A), len(B)) + 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1 = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        n1_n2 = n1 + n2\n",
    "        ans = 0\n",
    "        for i in range(n1_n2):\n",
    "            if n1 - i < 0:\n",
    "                n1_diff = 0\n",
    "            else:\n",
    "                n1_diff = n1 - i\n",
    "            if n1 - i > 0:\n",
    "                n2_diff = 0\n",
    "            else:\n",
    "                n2_diff = i - n1\n",
    "            Max = 0\n",
    "            lenght = 0\n",
    "            j = 0\n",
    "            while (n1_diff+j<n1 and n2_diff+j<n2):\n",
    "                if nums1[n1_diff+j] == nums2[n2_diff+j]:\n",
    "                    lenght+=1\n",
    "                else:\n",
    "                    if lenght:\n",
    "                        Max = max(lenght,Max)\n",
    "                        lenght= 0\n",
    "                j+=1\n",
    "            Max = max(lenght,Max)\n",
    "            ans = max(ans,Max)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dp = [0] * (len(nums2) + 1)\n",
    "        result = 0\n",
    "        for i in range(1, len(nums1)+1):\n",
    "            for j in range(len(nums2), 0, -1):\n",
    "                if nums1[i-1] == nums2[j-1]:\n",
    "                    dp[j] = dp[j-1] + 1\n",
    "                else:\n",
    "                    dp[j] = 0 #注意这里不相等的时候要有赋0的操作\n",
    "                result = max(result, dp[j])\n",
    "            \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        dp = [0] * (n + 1)\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums2) + 1):\n",
    "            for j in range(n, 0, -1):\n",
    "                if nums2[i - 1] == nums1[j - 1]:\n",
    "                    dp[j] = dp[j - 1] + 1\n",
    "                    if dp[j] > ans:\n",
    "                        ans = dp[j]\n",
    "                else:\n",
    "                    dp[j] = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n,m = len(nums1),len(nums2)\n",
    "        ans = 0\n",
    "        dp = [0]*(m+1)\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(m,0,-1):\n",
    "                if nums1[i-1] == nums2[j-1]:\n",
    "                    dp[j] = dp[j-1]+1\n",
    "                else:\n",
    "                    dp[j] = 0\n",
    "                ans = max(ans, dp[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        def toString(nums):\n",
    "            return ''.join([chr(num) for num in nums])\n",
    "            \n",
    "        def check(length):\n",
    "            set1 = set()\n",
    "            for i in range(length,m+1):\n",
    "                set1.add(str1[i-length:i])\n",
    "            for i in range(length,n+1):\n",
    "                if str2[i-length:i] in set1:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        m,n = len(nums1), len(nums2)\n",
    "        str1, str2 = toString(nums1), toString(nums2)\n",
    "        left, right = 0, min(m,n)\n",
    "        res = 0\n",
    "        while left<=right:\n",
    "            mid = left+(right-left)//2\n",
    "            if check(mid):\n",
    "                res = mid\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 暴力求解方法\n",
    "    def _findLength(self, nums1: List[int], nums2: List[int]) -> int:    \n",
    "        # 创建一个哈希表保存nums2从value到index的映射\n",
    "        hashmap = {}\n",
    "        for x in range(len(nums2)):\n",
    "            if nums2[x] in hashmap:\n",
    "                vlist = hashmap[nums2[x]]\n",
    "                vlist.append(x)\n",
    "            else:\n",
    "                hashmap[nums2[x]] = [x]\n",
    "        # print(hashmap)\n",
    "        # 创建一个dp数组，长度为nums1和nums2中较小的数组的长度\n",
    "        dp = [0 for _ in range(len(nums1))]\n",
    "\n",
    "        # print(dp)\n",
    "\n",
    "        # 从nums1的第二个元素开始遍历\n",
    "        for i in range(len(nums1)):\n",
    "            # 如果nums1[i]在nums2中出现过\n",
    "            if nums1[i] in hashmap:\n",
    "                _max = 0\n",
    "                for _i in hashmap[nums1[i]]:\n",
    "                    _m = min(_i,i) + 1\n",
    "                    _d = 0\n",
    "                    # print(_i,i)\n",
    "                    while _d < _m:\n",
    "                        if nums1[i-_d] == nums2[_i -_d]:\n",
    "                            _d += 1\n",
    "                        else:\n",
    "                            break\n",
    "                    if _d > _max:\n",
    "                            _max  = _d\n",
    "                dp[i] = _max\n",
    "\n",
    "        # print(dp)\n",
    "        _max = 0\n",
    "        for i in dp:\n",
    "            if i > _max:\n",
    "                _max = i\n",
    "\n",
    "        return _max\n",
    "\n",
    "    # 采用动态规划\n",
    "    def _findLength(self, nums1: List[int], nums2: List[int]) -> int:    \n",
    "        dp = [[0 for _ in range(len(nums2) + 1)] for _ in range(len(nums1) + 1)]\n",
    "        _max = 0\n",
    "        for i in range(1,len(nums1) +1):\n",
    "            for j in range(1,len(nums2) +1):\n",
    "                if nums1[i-1] == nums2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                    if _max < dp[i][j]:\n",
    "                        _max = dp[i][j]\n",
    "        # print(dp)\n",
    "        return _max\n",
    "\n",
    "    # 采用二分 + 哈希\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "\n",
    "        base, mod = 113, 10**9 + 9\n",
    "        def check(length: int) -> bool:\n",
    "            # hashA = 0\n",
    "            # for i in range(length):\n",
    "            #     hashA = (hashA * base + A[i]) % mod\n",
    "            # bucketA = {hashA}\n",
    "            # mult = pow(base, length - 1, mod)\n",
    "            # for i in range(length, len(A)):\n",
    "            #     hashA = ((hashA - A[i - length] * mult) * base + A[i]) % mod\n",
    "            #     bucketA.add(hashA)\n",
    "\n",
    "            bucketA = {-1}\n",
    "            for i in range(len(A) - length + 1):\n",
    "                hashA = ''\n",
    "                for x in A[i:i+length]:\n",
    "                    hashA += str(x)\n",
    "                bucketA.add(hashA)\n",
    "            \n",
    "            # print(bucketA)\n",
    "\n",
    "            # hashB = 0\n",
    "            # for i in range(length):\n",
    "            #     hashB = (hashB * base + B[i]) % mod\n",
    "            # if hashB in bucketA:\n",
    "            #     return True\n",
    "            # for i in range(length, len(B)):\n",
    "            #     hashB = ((hashB - B[i - length] * mult) * base + B[i]) % mod\n",
    "            #     if hashB in bucketA:\n",
    "            #         return True\n",
    "            for i in range(len(B) - length + 1):\n",
    "                hashB = ''\n",
    "                for x in B[i:i+length]:\n",
    "                    hashB += str(x)\n",
    "                if hashB in bucketA:\n",
    "                    # print(hashB,bucketA,length)\n",
    "                    return True\n",
    "\n",
    "            \n",
    "            return False\n",
    "\n",
    "        left, right = 0, min(len(A), len(B))\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                print(mid)\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        if len(nums1) > len(nums2):\n",
    "            nums1, nums2 = nums2, nums1\n",
    "        n = len(nums1)\n",
    "        m = len(nums2)\n",
    "        l, r = 0, n + 1\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            s = set()\n",
    "            for i in range(n-mid+1):\n",
    "                s.add(tuple(nums1[i:i+mid]))\n",
    "            for j in range(m-mid+1):\n",
    "                if tuple(nums2[j:j+mid]) in s:\n",
    "                    l = mid + 1\n",
    "                    break\n",
    "            else:\n",
    "                r = mid\n",
    "        return l - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, a: List[int], b: List[int]) -> int:\n",
    "        def suffixArray(s):\n",
    "            if s == None or len(s) == 0:\n",
    "                return None\n",
    "            allSuffix = []\n",
    "            for i in range(len(s)):\n",
    "                allSuffix.append([s[i:], i])\n",
    "            sortedList = sorted(allSuffix)\n",
    "            SA = [w[1] for w in sortedList]\n",
    "            return SA\n",
    "        n1, n2 = len(a), len(b)\n",
    "        s = bytearray(a) + bytearray([100]) + bytearray(b)\n",
    "        n = len(s)\n",
    "\n",
    "        # 求出后缀数组和高度数组\n",
    "        sa = suffixArray(s)\n",
    "        rank = [0] * n\n",
    "        for i in range(n):\n",
    "            rank[sa[i]] = i\n",
    "        height = [0] * n\n",
    "        h = 0\n",
    "        for i, rk in enumerate(rank):\n",
    "            if h > 0:\n",
    "                h -= 1\n",
    "            if rk > 0:\n",
    "                j = sa[rk-1]\n",
    "                while i+h < n and j+h < n and s[i+h] == s[j+h]:\n",
    "                    h += 1\n",
    "            height[rk] = h\n",
    "\n",
    "        # 若高度对应的 sa[i-1] 和 sa[i] 属于不同数组，则更新答案的最大值\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            if (sa[i] < n1) != (sa[i-1] < n1) and height[i] > ans:\n",
    "                ans = height[i]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        if len(nums1) > len(nums2):\n",
    "            nums1, nums2 = nums2, nums1\n",
    "\n",
    "        def check(size):\n",
    "            nums1_set = set()\n",
    "            for start in range(len(nums1)+1 - size):\n",
    "                nums1_set.add(tuple(nums1[start:start+size]))\n",
    "\n",
    "            for start in range(len(nums2)+1 - size):\n",
    "                if tuple(nums2[start:start+size]) in nums1_set:\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        left, right = 0, len(nums1)\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "# 作者：117503445\n",
    "# 链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/solutions/2402681/er-fen-ha-xi-ji-yu-set-he-tuplechao-ji-j-rxfd/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        if not set(nums1)&set(nums2):\n",
    "            return 0\n",
    "\n",
    "        global res\n",
    "        res = 1\n",
    "\n",
    "        def tool(nums1,nums2):\n",
    "            global res\n",
    "            if min(len(nums1),len(nums2))==0:\n",
    "                return\n",
    "            for left in range(len(nums2)):\n",
    "                if nums2[left:left+res]==nums1[:res]:\n",
    "                    while (left+res)<len(nums2) and res<len(nums1) and nums2[left+res]==nums1[res]:\n",
    "                        res += 1\n",
    "            if res==min(len(nums1),len(nums2)):\n",
    "                return\n",
    "            tool(nums1[1:],nums2)\n",
    "        \n",
    "        tool(nums1,nums2)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def move(self,numsStable,numsMove,start):\n",
    "        if start == len(numsStable):\n",
    "            return []\n",
    "        cur,nex,i = [],[],0\n",
    "        temp = []\n",
    "        j = start\n",
    "        while j < len(numsStable) and i < len(numsMove) :\n",
    "            if numsStable[j] == numsMove[i]:\n",
    "                temp.append(numsStable[j])\n",
    "            else :\n",
    "                cur = cur if len(cur)>len(temp) else temp\n",
    "                temp = []\n",
    "            i += 1\n",
    "            j += 1\n",
    "        cur = cur if len(cur)>len(temp) else temp\n",
    "        nex = self.move(numsStable,numsMove,start+1)\n",
    "        return cur if len(cur)>len(nex) else nex\n",
    "\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        temp1,temp2 = [],[]\n",
    "        temp1=self.move(nums1,nums2,0)\n",
    "        temp2=self.move(nums2,nums1,0)\n",
    "        return max(len(temp1),len(temp2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\r\n",
    "        len_A = len(A)\r\n",
    "        len_B = len(B)\r\n",
    "        res = [[False] * len_B for _ in range(len_A)]\r\n",
    "        for i in range(len_A):\r\n",
    "            for j in range(len_B):\r\n",
    "                if A[i] == B[j]:\r\n",
    "                    res[i][j] = True\r\n",
    "        ans = 0\r\n",
    "        for j in range(len_B):\r\n",
    "            i = 0\r\n",
    "            t = 0\r\n",
    "            idx = []\r\n",
    "            while i < len_A and j < len_B:\r\n",
    "                if  res[i][j]:\r\n",
    "                    t += 1\r\n",
    "                else:\r\n",
    "                    t = 0\r\n",
    "                idx.append(t)\r\n",
    "                i += 1\r\n",
    "                j += 1\r\n",
    "            if len(idx) > 0:\r\n",
    "                ans = max(ans, max(idx))\r\n",
    "        \r\n",
    "        for i in range(len_A):\r\n",
    "            j = 0\r\n",
    "            t = 0\r\n",
    "            idx = []\r\n",
    "            while i < len_A and j < len_B:\r\n",
    "                if  res[i][j]:\r\n",
    "                    t += 1\r\n",
    "                else:\r\n",
    "                    t = 0\r\n",
    "                idx.append(t)\r\n",
    "                i += 1\r\n",
    "                j += 1\r\n",
    "            if len(idx) > 0:\r\n",
    "                ans = max(ans, max(idx))\r\n",
    "        return ans\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "\n",
    "        def check(length: int) -> bool:\n",
    "            setA = set()\n",
    "            for r in range(min(length, len(A)), len(A)+1):\n",
    "                setA.add(tuple(A[r - length:r]))\n",
    "\n",
    "            setB = set()\n",
    "            for r in range(min(length, len(B)), len(B)+1):\n",
    "                tmp = tuple(B[r - length:r])\n",
    "                if tmp in setA: return True\n",
    "                setB.add(tmp)\n",
    "\n",
    "            return False\n",
    "\n",
    "        left, right = 1, min(len(A), len(B))\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        if len(set(nums1)&set(nums2))==0:\n",
    "            return 0\n",
    "        m,n=len(nums1),len(nums2)\n",
    "        def check(mid):\n",
    "            s1=set()\n",
    "            s2=set()\n",
    "            for start in range(m-mid+1):\n",
    "                s1.add(tuple(nums1[start:start+mid]))\n",
    "            for start in range(n-mid+1):\n",
    "                s2.add(tuple(nums2[start:start+mid]))\n",
    "            return len(s1&s2)>0\n",
    "        #二分枚举最长长度k\n",
    "        cmin=1\n",
    "        cmax=min(m,n)\n",
    "        while cmin<=cmax:\n",
    "            mid=(cmin+cmax)//2\n",
    "            if check(mid):\n",
    "                cur=mid\n",
    "                cmin=mid+1\n",
    "            else:\n",
    "                cmax=mid-1\n",
    "        return cur\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        ans = 0\n",
    "        # 取%的那一行在外层循环，需要频繁改变的在内存\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i%2][j] = dp[(i-1)%2][j-1] + 1 if nums1[i-1] == nums2[j-1] else 0\n",
    "                ans=max(ans,dp[i%2][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        matrix = [[False]*len(nums1) for _ in range(len(nums2))]\n",
    "        for x in range(len(nums1)):\n",
    "            for y in range(len(nums2)):\n",
    "                if nums1[x] == nums2[y]:\n",
    "                    matrix[y][x] = True\n",
    "\n",
    "        output = 0\n",
    "        tmp = 0\n",
    "        for i in range(len(nums2)):\n",
    "            y = i\n",
    "            x = 0\n",
    "            while y < len(nums2) and x < len(nums1):\n",
    "                if matrix[y][x]:\n",
    "                    tmp += 1\n",
    "                    x += 1\n",
    "                    y += 1\n",
    "                else:\n",
    "                    output = max(output, tmp)\n",
    "                    tmp = 0\n",
    "                    x += 1\n",
    "                    y += 1\n",
    "            output = max(output, tmp)\n",
    "            tmp = 0\n",
    "\n",
    "        for i in range(len(nums1)):\n",
    "            y = 0\n",
    "            x = i\n",
    "            while y < len(nums2) and x < len(nums1):\n",
    "                if matrix[y][x]:\n",
    "                    tmp += 1\n",
    "                    x += 1\n",
    "                    y += 1\n",
    "                else:\n",
    "                    output = max(output, tmp)\n",
    "                    tmp = 0\n",
    "                    x += 1\n",
    "                    y += 1\n",
    "            output = max(output, tmp)\n",
    "            tmp = 0\n",
    "\n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dp=[[0 for j in range(len(nums2))] for i in range(len(nums1))]\n",
    "        # print(dp)\n",
    "        max_len=0\n",
    "        for i in range(len(nums1)):\n",
    "            for j in range(len(nums2)):\n",
    "                if dp[i][j]==0:\n",
    "                    if nums1[i]==nums2[j]:\n",
    "                        dp[i][j]=1\n",
    "                        this_len=1\n",
    "                        next_i=i+1\n",
    "                        next_j=j+1\n",
    "                        while(next_i<len(nums1) and next_j<len(nums2)):\n",
    "                            if nums1[next_i]==nums2[next_j]:\n",
    "                                dp[next_i][next_j]=1\n",
    "                                this_len+=1\n",
    "                                next_i+=1\n",
    "                                next_j+=1\n",
    "                            else:\n",
    "                                break\n",
    "                        if this_len>max_len:\n",
    "                            max_len=this_len\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dp = [[False]*len(nums1) for _ in range(len(nums2))]\n",
    "        for i in range(len(nums2)):\n",
    "            for j in range(len(nums1)):\n",
    "                if nums1[j] == nums2[i]:\n",
    "                    dp[i][j] = True\n",
    "        res = 0\n",
    "\n",
    "        for i in range(len(nums1)):\n",
    "            cur = 0\n",
    "            start = [-1,i-1]\n",
    "            for j in range(len(nums2)):\n",
    "                start[0], start[1] = start[0] + 1, start[1] + 1\n",
    "                if start[1]>len(nums1)-1 or start[0]>len(nums2)-1:\n",
    "                    break\n",
    "                if dp[start[0]][start[1]] == True:\n",
    "                    cur += 1\n",
    "                    res = max(cur,res)\n",
    "                else:\n",
    "                    cur = 0\n",
    "        for i in range(1,len(nums2)):\n",
    "            cur = 0\n",
    "            start = [i-1,-1]\n",
    "            for j in range(len(nums1)):\n",
    "                start[0], start[1] = start[0] + 1, start[1] + 1\n",
    "                if start[1] > len(nums1) - 1 or start[0] > len(nums2) - 1:\n",
    "                    break\n",
    "                if dp[start[0]][start[1]] == True:\n",
    "                    cur += 1\n",
    "                    res = max(cur,res)\n",
    "                else:\n",
    "                    cur = 0\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dp = [[1 if nums1[i] == nums2[j] else 0 for j in range(len(nums2))]  for i in range(len(nums1))]\n",
    "        m, n = len(dp), len(dp[0])\n",
    "\n",
    "        res = 0\n",
    "        x, y = m - 1, 0\n",
    "        while x >= 0:\n",
    "            i, j = x, y\n",
    "            temp = 0\n",
    "            while i < m and j < n:\n",
    "                temp = temp + 1 if dp[i][j] else 0\n",
    "                res = max(res, temp)\n",
    "                i += 1\n",
    "                j += 1\n",
    "            x -= 1\n",
    "        \n",
    "        x, y = 0, 1\n",
    "        while y < n:\n",
    "            i, j = x, y\n",
    "            temp = 0\n",
    "            while i < m and j < n:\n",
    "                temp = temp + 1 if dp[i][j] else 0\n",
    "                res = max(res, temp)\n",
    "                i += 1\n",
    "                j += 1\n",
    "            y += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        table = [[0 for i in range(len(nums1))] for i in range(len(nums2))]\n",
    "        def sum_cross(table,pos):\n",
    "            res = 0\n",
    "            cur_sum = 0\n",
    "            row = len(table)\n",
    "            col = len(table[0])\n",
    "            cur_x = pos[0]\n",
    "            cur_y = pos[1]\n",
    "            while cur_x < row and cur_y < col:\n",
    "                if table[cur_x][cur_y] !=0:\n",
    "                    cur_sum += table[cur_x][cur_y]\n",
    "                    if res < cur_sum:\n",
    "                        res = cur_sum\n",
    "                else:\n",
    "                    cur_sum = 0\n",
    "                cur_x += 1\n",
    "                cur_y += 1\n",
    "            return res\n",
    "        # print(table)\n",
    "        for j in range(len(nums1)):\n",
    "            for i in range(len(nums2)):\n",
    "                if nums1[j] == nums2[i]:\n",
    "                    table[i][j] = 1\n",
    "        starts = [[0,0]] + [[0,i] for i in range(1,len(nums1))] + [[i,0] for i in range(1,len(nums2))]\n",
    "        res = 0\n",
    "        for i in starts:\n",
    "            cur = sum_cross(table,i)\n",
    "            if cur > res:\n",
    "                res = cur\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "        len_a = len(A)\n",
    "        len_b = len(B)\n",
    "        m_list = []\n",
    "        for i in range(1,len_a+len_b):\n",
    "            if i <= len_b:\n",
    "                m = 0\n",
    "                for j in zip(A[0:i], B[len_b-i:]):\n",
    "                    if j[0] == j[1]:\n",
    "                        m += 1\n",
    "                    else:\n",
    "                        m_list.append(m)\n",
    "                        m = 0\n",
    "                m_list.append(m)\n",
    "            else:\n",
    "                m = 0\n",
    "                for j in zip(A[i-len_a:], B[:len_a+len_b-i]):\n",
    "                    if j[0] == j[1]:\n",
    "                        m += 1\n",
    "                    else:\n",
    "                        m_list.append(m)\n",
    "                        m = 0\n",
    "                m_list.append(m)\n",
    "        return max(m_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        length1=len(nums1)\n",
    "        length2=len(nums2)\n",
    "        a=min(length1,length2)\n",
    "        b=max(length1,length2)\n",
    "        start= 0\n",
    "        end=a\n",
    "        List1=[]\n",
    "        count=0\n",
    "        if length1>=length2:\n",
    "            maxx=nums1\n",
    "            minn=nums2\n",
    "        else:\n",
    "            maxx=nums2\n",
    "            minn=nums1\n",
    "\n",
    "        while start<len(maxx):\n",
    "            c=maxx[start:end]\n",
    "            for i in range(len(c)):\n",
    "                if c[i]==minn[i]:\n",
    "                    count+=1\n",
    "                else:\n",
    "                    List1.append(count)\n",
    "                    count=0\n",
    "            List1.append(count)\n",
    "            count=0\n",
    "            start+=1\n",
    "            end+=1\n",
    "        if length2==length1:\n",
    "            start= 0\n",
    "            end=a\n",
    "            count=0\n",
    "            while start<len(maxx):\n",
    "                c=minn[start:end]\n",
    "                for i in range(len(c)):\n",
    "                    if c[i]==maxx[i]:\n",
    "                        count+=1\n",
    "                    else:\n",
    "                        List1.append(count)\n",
    "                        count=0\n",
    "                List1.append(count)\n",
    "                count=0\n",
    "                start+=1\n",
    "                end+=1\n",
    "\n",
    "\n",
    "        return max(List1)\n",
    "          \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, is_leaf, color=None):\n",
    "        self.children = {}\n",
    "        self.is_leaf = is_leaf\n",
    "        self.start = None\n",
    "        self.end = None\n",
    "        self.suffix_link = None\n",
    "        # for color set size problem\n",
    "        self.color = color\n",
    "        self.leaf_count = None\n",
    "        self.cpl_count = 0\n",
    "        self.duplicate = 0\n",
    "        self.color_set_size = 0\n",
    "        # for lca problem\n",
    "        self.pre_order = 0\n",
    "        self.in_label = 0\n",
    "        self.level = 0\n",
    "        self.ascendant = 0\n",
    "        self.father = None\n",
    "    \n",
    "    def __repr__(self):\n",
    "        str_val = \"({}, {}, {}, {})\".format(self.pre_order, self.color, self.cpl_count, self.color_set_size)\n",
    "        return str_val\n",
    "\n",
    "def left_most_1_bit(n):\n",
    "    n |= (n >> 1)\n",
    "    n |= (n >> 2)\n",
    "    n |= (n >> 4)\n",
    "    n |= (n >> 8)\n",
    "    n |= (n >> 16)\n",
    "    return n - (n >> 1)\n",
    "\n",
    "def right_most_1_bit(n):\n",
    "    return (n ^ (n - 1)) & n \n",
    "\n",
    "def get_in_label_b(node_x, node_y):\n",
    "    in_label_x = node_x.in_label\n",
    "    in_label_y = node_y.in_label\n",
    "    bit = left_most_1_bit(in_label_x^in_label_y)\n",
    "    left_mask = ~((bit << 1) - 1)\n",
    "    in_label_b = (in_label_x & left_mask) | bit\n",
    "    return in_label_b\n",
    "\n",
    "def get_in_label_z(node_x, node_y, in_label_b):\n",
    "    #print(\"enter get_in_label_z ~\")\n",
    "    #print(\"{:0>7}\".format(bin(in_label_b)[2:]))\n",
    "    bit = right_most_1_bit(in_label_b)\n",
    "    mask = ~(bit - 1)\n",
    "    #print(\"bit = {}, mask = {}\".format(bit, mask))\n",
    "    common_ascendant = (node_x.ascendant & node_y.ascendant) & mask\n",
    "    #print(\"mask:{:1>7}, common_ascendant:{:0>7}\".format(bin(mask)[3:], bin(common_ascendant)[2:]))\n",
    "    bit = right_most_1_bit(common_ascendant)\n",
    "    #print(\"bit2 = {:0>7}\".format(bin(bit)[2:]))\n",
    "    mask = ~((bit << 1) - 1)\n",
    "    #print(\"mask2 : {:1>7}, node_x.in_label : {:0>7}\".format(bin(mask)[3:], bin(node_x.in_label)[2:]))\n",
    "    in_label_z = (node_x.in_label & mask) | bit\n",
    "    return in_label_z\n",
    "\n",
    "def find_x_hat(in_label_z, node, head):\n",
    "    if node.in_label == in_label_z:\n",
    "        return node\n",
    "    bit_label_z = right_most_1_bit(in_label_z)\n",
    "    mask = bit_label_z - 1\n",
    "    bit_ascendant = left_most_1_bit(node.ascendant & mask)\n",
    "    mask = ~((bit_ascendant << 1) - 1)\n",
    "    in_label_w = (node.in_label & mask) | bit_ascendant\n",
    "    #print(\"in_label_w : {:0>5}\".format(bin(in_label_w)[2:]))\n",
    "    w = head[in_label_w]\n",
    "    return w.father\n",
    "\n",
    "class GeneralizedSuffixTree:\n",
    "    def __init__(self, strings):\n",
    "        self.sequence = []\n",
    "        sep_id = 0\n",
    "        for string in strings:\n",
    "            self.sequence.extend(list(string))\n",
    "            self.sequence.append(sep_id)\n",
    "            sep_id += 1\n",
    "        self.root = None\n",
    "        self.active_node = None\n",
    "        self.active_edge = -1\n",
    "        self.active_length = 0\n",
    "        self.remaining_suffix_count = 0\n",
    "        self.leaf_end = -1\n",
    "        # for color set size problem\n",
    "        self.cur_color = None\n",
    "        self.leaf_list = None\n",
    "        self.last_leaf = None\n",
    "        # for lca problem\n",
    "        self.head = None\n",
    "        \n",
    "    def new_node(self, start, end=None, is_leaf=False):\n",
    "        if is_leaf:\n",
    "            node = Node(True, color=self.cur_color)\n",
    "        else:\n",
    "            node = Node(False)\n",
    "        node.suffix_link = self.root\n",
    "        node.start = start\n",
    "        node.end = end\n",
    "        return node\n",
    "        \n",
    "    def edge_length(self, node):\n",
    "        if node.is_leaf:\n",
    "            return self.leaf_end - node.start + 1\n",
    "        else:\n",
    "            return node.end - node.start + 1\n",
    "    \n",
    "    def walk_down(self, current_node):\n",
    "        length = self.edge_length(current_node)\n",
    "        if self.active_length >= length:\n",
    "            self.active_edge += length\n",
    "            self.active_length -= length\n",
    "            self.active_node = current_node\n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    def extend_suffix_tree(self, pos):\n",
    "        self.leaf_end = pos\n",
    "        self.remaining_suffix_count += 1\n",
    "        last_new_node = None\n",
    "        while self.remaining_suffix_count > 0:\n",
    "            if self.active_length == 0:\n",
    "                self.active_edge = pos\n",
    "            if self.active_node.children.get(self.sequence[self.active_edge]) is None:\n",
    "                self.active_node.children[self.sequence[self.active_edge]] = self.new_node(pos, is_leaf=True)\n",
    "                if last_new_node is not None:\n",
    "                    last_new_node.suffix_link = self.active_node\n",
    "                    last_new_node = None\n",
    "            else:\n",
    "                _next = self.active_node.children.get(self.sequence[self.active_edge])\n",
    "                if self.walk_down(_next):\n",
    "                    continue\n",
    "                if self.sequence[_next.start + self.active_length] == self.sequence[pos]:\n",
    "                    if last_new_node is not None and self.active_node != self.root:\n",
    "                        last_new_node.suffix_link = self.active_node\n",
    "                        last_new_node = None\n",
    "                    self.active_length += 1\n",
    "                    break\n",
    "                split_end = _next.start + self.active_length - 1\n",
    "                split_node = self.new_node(_next.start, split_end)\n",
    "                self.active_node.children[self.sequence[self.active_edge]] = split_node\n",
    "                split_node.children[self.sequence[pos]] = self.new_node(pos, is_leaf=True)\n",
    "                _next.start += self.active_length\n",
    "                split_node.children[self.sequence[_next.start]] = _next\n",
    "                if last_new_node is not None:\n",
    "                    last_new_node.suffix_link = split_node\n",
    "                last_new_node = split_node\n",
    "            self.remaining_suffix_count -= 1\n",
    "            if self.active_node == self.root and self.active_length > 0:\n",
    "                self.active_length -= 1\n",
    "                self.active_edge = pos - self.remaining_suffix_count + 1\n",
    "            elif self.active_node != self.root:\n",
    "                self.active_node = self.active_node.suffix_link\n",
    "            \n",
    "    def build_suffix_tree(self):\n",
    "        self.root = self.new_node(-1, -1)\n",
    "        self.active_node = self.root\n",
    "        self.cur_color = 0\n",
    "        for i, e in enumerate(self.sequence):\n",
    "            self.extend_suffix_tree(i)\n",
    "            if isinstance(e, int):\n",
    "                self.cur_color += 1\n",
    "\n",
    "    def dfs_to_get_leaf_count(self, node):\n",
    "        leaf_count = 0\n",
    "        if node.is_leaf:\n",
    "            leaf_count = 1\n",
    "        else:\n",
    "            for k, child in node.children.items():\n",
    "                leaf_count += self.dfs_to_get_leaf_count(child)\n",
    "        node.leaf_count = leaf_count\n",
    "        return leaf_count\n",
    "    \n",
    "    def get_leaf_count(self):\n",
    "        self.dfs_to_get_leaf_count(self.root)\n",
    "        \n",
    "    def dfs_to_get_leaf_list(self, node):    \n",
    "        if node.is_leaf:\n",
    "            self.leaf_list.append(node)\n",
    "        else:\n",
    "            for k, child in node.children.items():\n",
    "                self.dfs_to_get_leaf_list(child)\n",
    "        \n",
    "    def get_leaf_list(self):\n",
    "        self.leaf_list = []\n",
    "        self.dfs_to_get_leaf_list(self.root)\n",
    "        \n",
    "    def get_last_leaf(self):\n",
    "        last_leaf_of_color = [None for i in range(self.cur_color)]\n",
    "        self.last_leaf = [None for i in range(len(self.leaf_list))]\n",
    "        for i, node in enumerate(self.leaf_list):\n",
    "            self.last_leaf[i] = last_leaf_of_color[node.color]\n",
    "            last_leaf_of_color[node.color] = i\n",
    "    \n",
    "    def dfs_to_get_in_label(self, root, order, level, father):\n",
    "        root.pre_order = order\n",
    "        root.level = level\n",
    "        root.father = father\n",
    "        in_label = order\n",
    "        for k, child in root.children.items():\n",
    "            order, in_label_ret = self.dfs_to_get_in_label(child, order + 1, level + 1, root)\n",
    "            if right_most_1_bit(in_label_ret) > right_most_1_bit(in_label):\n",
    "                in_label = in_label_ret\n",
    "        root.in_label = in_label\n",
    "        return order, root.in_label\n",
    "    \n",
    "    def dfs_to_compute_ascendant(self, root, ascendant):\n",
    "        root.ascendant = ascendant | ((root.in_label ^ (root.in_label - 1)) & root.in_label)\n",
    "        for k, child in root.children.items():\n",
    "            self.dfs_to_compute_ascendant(child, root.ascendant)\n",
    "    \n",
    "    def dfs_to_get_head(self, root, head):\n",
    "        if root.in_label not in head:\n",
    "            head[root.in_label] = root\n",
    "        for k, child in root.children.items():\n",
    "            self.dfs_to_get_head(child, head)\n",
    "            \n",
    "    def preprocess_lca(self):\n",
    "        self.dfs_to_get_in_label(self.root, 1, 0, None)\n",
    "        self.dfs_to_compute_ascendant(self.root, 0)\n",
    "        self.head = {}\n",
    "        self.dfs_to_get_head(self.root, self.head)\n",
    "    \n",
    "    def query_lca(self, node_x, node_y):\n",
    "        if node_x.in_label == node_y.in_label:\n",
    "            if node_x.level < node_y.level:\n",
    "                return node_x\n",
    "            else:\n",
    "                return node_y\n",
    "        in_label_b = get_in_label_b(node_x, node_y)\n",
    "        in_label_z = get_in_label_z(node_x, node_y, in_label_b)\n",
    "        #print(\"in_label_b : {:0>7}, in_label_z : {:0>7}\".format(bin(in_label_b)[2:], bin(in_label_z)[2:]))\n",
    "        x_hat = find_x_hat(in_label_z, node_x, self.head)\n",
    "        y_hat = find_x_hat(in_label_z, node_y, self.head)\n",
    "        if x_hat.level < y_hat.level:\n",
    "            return x_hat\n",
    "        else:\n",
    "            return y_hat\n",
    "        \n",
    "    def get_color_pair_lca_count(self):\n",
    "        self.preprocess_lca()\n",
    "        for leaf, last_leaf in zip(self.leaf_list, self.last_leaf):\n",
    "            if last_leaf is None:\n",
    "                continue\n",
    "            #if (leaf.pre_order != 9) or (self.leaf_list[last_leaf].pre_order != 6):\n",
    "            #    continue\n",
    "            #print(\"leaf : {}, last leaf : {}\".format(leaf.pre_order, self.leaf_list[last_leaf].pre_order))\n",
    "            lca_node = self.query_lca(leaf, self.leaf_list[last_leaf])\n",
    "            #print(\"lca_node : {}\".format(lca_node.pre_order))\n",
    "            lca_node.cpl_count += 1\n",
    "    \n",
    "    def dfs_to_compute_duplicate_count(self, node):\n",
    "        node.duplicate = node.cpl_count\n",
    "        for k, child in node.children.items():\n",
    "            node.duplicate += self.dfs_to_compute_duplicate_count(child)\n",
    "        return node.duplicate\n",
    "    \n",
    "    def compute_duplicate_count(self):\n",
    "        self.dfs_to_compute_duplicate_count(self.root)\n",
    "        \n",
    "    def dfs_to_compute_color_set_size(self, node):\n",
    "        node.color_set_size = node.leaf_count - node.duplicate\n",
    "        for k, child in node.children.items():\n",
    "            self.dfs_to_compute_color_set_size(child)\n",
    "            \n",
    "    def compute_color_set_size(self):\n",
    "        self.dfs_to_compute_color_set_size(self.root)\n",
    "        \n",
    "    def dfs_to_get_common_str_list(self, node, prefix_str, common_str_list, k, length):\n",
    "        if node.is_leaf:\n",
    "            return 0\n",
    "        if node is not self.root:\n",
    "            prefix_str = prefix_str + ''.join(self.sequence[node.start:node.end+1])\n",
    "        if node.color_set_size < k:\n",
    "            return 0\n",
    "        cnt = 0\n",
    "        for _, child in node.children.items():\n",
    "            cnt += self.dfs_to_get_common_str_list(child, prefix_str, common_str_list, k, length)\n",
    "        if cnt > 0:\n",
    "            return cnt\n",
    "        if len(prefix_str) >= length and node.color_set_size >= k:\n",
    "            common_str_list.append(prefix_str)\n",
    "            #cnt += 1\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n",
    "            \n",
    "    def get_common_str(self, k, length):\n",
    "        self.build_suffix_tree()\n",
    "        self.get_leaf_count()\n",
    "        self.get_leaf_list()\n",
    "        self.get_last_leaf()\n",
    "        self.get_color_pair_lca_count()\n",
    "        self.compute_duplicate_count()\n",
    "        self.compute_color_set_size()\n",
    "        common_str_list = []\n",
    "        self.dfs_to_get_common_str_list(self.root, \"\", common_str_list, k, length)\n",
    "        return common_str_list\n",
    "\n",
    "    def dfs_to_get_longest_common_str(self, node, k, prefix_str):\n",
    "        if node.is_leaf:\n",
    "            return \"\"\n",
    "        if node is not self.root:\n",
    "            prefix_str = prefix_str + ''.join(self.sequence[node.start:node.end+1])\n",
    "        if node.color_set_size != 2:\n",
    "            return \"\"\n",
    "        ans = prefix_str\n",
    "        for _, child in node.children.items():\n",
    "            ret = self.dfs_to_get_longest_common_str(child, k, prefix_str)\n",
    "            if len(ret) > len(ans):\n",
    "                ans = ret\n",
    "        return ans\n",
    "    \n",
    "    def get_longest_common_str(self, k):\n",
    "        self.build_suffix_tree()\n",
    "        self.get_leaf_count()\n",
    "        self.get_leaf_list()\n",
    "        self.get_last_leaf()\n",
    "        self.get_color_pair_lca_count()\n",
    "        self.compute_duplicate_count()\n",
    "        self.compute_color_set_size()\n",
    "        lcs = self.dfs_to_get_longest_common_str(self.root, k, \"\")\n",
    "        return lcs\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "        str_a = ''.join([chr(e) for e in A])\n",
    "        str_b = ''.join([chr(e) for e in B])\n",
    "        suffix_tree = GeneralizedSuffixTree([str_a, str_b])\n",
    "        lcs = suffix_tree.get_longest_common_str(2)\n",
    "        return len(lcs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        l=[]\n",
    "        o=0\n",
    "        i=0\n",
    "        k=0\n",
    "        while k<len(nums1):\n",
    "            for j in range(len(nums2)):\n",
    "                if i+k>len(nums1)-1:\n",
    "                    break\n",
    "                if nums1[i+k]==nums2[j]:\n",
    "                    o+=1\n",
    "                else:\n",
    "                    l.append(o)\n",
    "                    o=0\n",
    "                i+=1\n",
    "            l.append(o)\n",
    "            i=0\n",
    "            o=0\n",
    "            k+=1\n",
    "        o=0\n",
    "        i=0\n",
    "        k=0\n",
    "        while k<len(nums2):\n",
    "            for j in range(len(nums1)):\n",
    "                if i+k>len(nums2)-1:\n",
    "                    break\n",
    "                if nums2[i+k]==nums1[j]:\n",
    "                    o+=1\n",
    "                else:\n",
    "                    l.append(o)\n",
    "                    o=0\n",
    "                i+=1\n",
    "            l.append(o)\n",
    "            i=0\n",
    "            o=0\n",
    "            k+=1\n",
    "        return max(l)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        if not nums1 or not nums2:\n",
    "            return 0\n",
    "            \n",
    "        res = 0\n",
    "        mems = [[-1] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]\n",
    "        for index1 in range(len(nums1)):\n",
    "            for index2 in range(len(nums2)):\n",
    "                if len(nums1) - index1 + 1 < res or len(nums2) - index2 + 1 < res:\n",
    "                    continue\n",
    "                res = max(res, self.search(nums1, nums2, index1, index2, mems))\n",
    "                \n",
    "        return res\n",
    "    \n",
    "    def search(self, nums1, nums2, index1, index2, mems):   \n",
    "        if mems[index1][index2] != -1:\n",
    "            return mems[index1][index2]\n",
    "        \n",
    "        if index1 == len(nums1) or index2 == len(nums2):\n",
    "            mems[index1][index2] = 0\n",
    "            return 0\n",
    "            \n",
    "        if nums1[index1] == nums2[index2]:\n",
    "            mems[index1][index2] = self.search(nums1, nums2, index1 + 1, index2 + 1, mems) + 1\n",
    "            return mems[index1][index2]\n",
    "        \n",
    "        mems[index1][index2] = 0\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        if not nums1 or not nums2:\n",
    "            return 0\n",
    "            \n",
    "        res = 0\n",
    "        mems = [[-1] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]\n",
    "        for index1 in range(len(nums1)):\n",
    "            for index2 in range(len(nums2)):\n",
    "                if len(nums1) - index1 + 1 < res or len(nums2) - index2 + 1 < res:\n",
    "                    continue\n",
    "                res = max(res, self.search(nums1, nums2, index1, index2, mems))\n",
    "                \n",
    "        return res\n",
    "    \n",
    "    def search(self, nums1, nums2, index1, index2, mems):   \n",
    "        if mems[index1][index2] != -1:\n",
    "            return mems[index1][index2]\n",
    "        \n",
    "        if index1 == len(nums1) or index2 == len(nums2):\n",
    "            mems[index1][index2] = 0\n",
    "            return 0\n",
    "            \n",
    "        if nums1[index1] == nums2[index2]:\n",
    "            mems[index1][index2] = self.search(nums1, nums2, index1 + 1, index2 + 1, mems) + 1\n",
    "            return mems[index1][index2]\n",
    "        \n",
    "        mems[index1][index2] = 0\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A, B) -> int:\n",
    "        b=self.jkl(A,B)\n",
    "        a=[]\n",
    "        c=[]\n",
    "        for i in range(len(A)):\n",
    "            d=[]\n",
    "            for j in range(len(A)-i):\n",
    "                if j<len(B):\n",
    "                  d.append(b[j+i][j])\n",
    "            a.append(d)\n",
    "        for i in range(len(B)):\n",
    "            d=[]\n",
    "            for j in range(len(B)-i):\n",
    "                if j<len(A):\n",
    "                  d.append(b[j][j+i])\n",
    "            a.append(d)\n",
    "        for i in range(len(a)):\n",
    "            d=self.xunzhao(a[i])\n",
    "            c.append(d)\n",
    "        return max(c)\n",
    "    def xunzhao(self,a):\n",
    "        if 1 not in a:\n",
    "            return 0\n",
    "        if 1 in a:\n",
    "            m=1\n",
    "            n=0\n",
    "            t=0\n",
    "            d=[]\n",
    "            for i in range(len(a)):\n",
    "                if a[i] == 0:\n",
    "                    m=0\n",
    "                if a[i]==1 and a[i-1]==0:\n",
    "                    m=1\n",
    "                    t=0\n",
    "                if a[i] == 1 and m == 1:\n",
    "                    n += 1\n",
    "                    t+=n\n",
    "                    n=0\n",
    "                    d.append(t)\n",
    "            return max(d)\n",
    "    def jkl(self,A,B):\n",
    "        m=0\n",
    "        b=[]\n",
    "        for i in range(len(A)):\n",
    "            f=A[i]\n",
    "            a=[]\n",
    "            for j in range(len(B)):\n",
    "                if f==B[j]:\n",
    "                  m=1\n",
    "                if f != B[j]:\n",
    "                  m=0\n",
    "                a.append(m)\n",
    "            b.append(a)\n",
    "        return b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        s = nums1+[-math.inf]+nums2\n",
    "        n = len(s)\n",
    "        arr = []\n",
    "        sa = []\n",
    "        rank = [0]*n\n",
    "        for i in range(n):\n",
    "            arr.append(s[i:])\n",
    "            sa.append(i)\n",
    "        arr,sa = [a for a,b in sorted(zip(arr,sa))],[b for a,b in sorted(zip(arr,sa))]\n",
    "        for idx,x in enumerate(sa):\n",
    "            rank[x] = idx\n",
    "        height = [0]*n\n",
    "        k = 0\n",
    "        for i in range(n):\n",
    "            if k:\n",
    "                k-=1\n",
    "            j = sa[rank[i]-1]\n",
    "            while i+k<n and j+k<n and (s[i+k]==s[j+k]):\n",
    "                k+=1\n",
    "            height[rank[i]]=k\n",
    "        ans = 0\n",
    "        m = len(nums1)+1\n",
    "        for i in range(1,n):\n",
    "            if (len(arr[i])>=m and len(arr[i-1])<m) or (len(arr[i])<m and len(arr[i-1])>=m):\n",
    "                ans = max(ans,height[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "\n",
    "    '''\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        import numpy as np \n",
    "        dp = [1 if nums2[0] == v1 else 0 for v1 in nums1]\n",
    "        max_v = max(dp)\n",
    "        for i, v in enumerate(nums2):\n",
    "            if i == 0:\n",
    "                continue\n",
    "\n",
    "            tmp = []\n",
    "            for j in range(len(nums1)):\n",
    "                t_v = None\n",
    "                if v == nums1[j]:\n",
    "                    if j == 0:\n",
    "                        t_v = 1\n",
    "                    else:\n",
    "                        t_v = dp[j - 1] + 1\n",
    "                else:\n",
    "                    t_v = 0\n",
    "                tmp.append(t_v)\n",
    "                \n",
    "                if t_v > max_v:\n",
    "                    max_v = t_v\n",
    "            dp = tmp\n",
    "\n",
    "        return (max_v)\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        import numpy as np\n",
    "        res = 0\n",
    "        for i in range(len(nums1) + len(nums2) - 1):\n",
    "            s = np.where(np.array(nums1[max(len(nums1) - i - 1, 0):min(len(nums1) - i - 1 + len(nums2), len(nums1))]) - np.array(nums2[max(i - len(nums1) + 1, 0):min(i + 1, len(nums2))]) == 0, \"0\", \"1\").tolist()\n",
    "            res = max(res, max([len(_) for _ in (\"\".join(s)).split(\"1\")]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "        len_a, len_b = len(A), len(B)\n",
    "        label = [[0] * (len_b + 1) for _ in range(len_a + 1)]\n",
    "        ans = 0\n",
    "        for i in range(0, len_a):\n",
    "            for j in range(0, len_b):\n",
    "                if A[i] == B[j] and (label[i][j] + len_a - i + 1) > ans and (label[i][j] + len_b - j + 1) > ans:\n",
    "                    label[i+1][j+1] = label[i][j] + 1\n",
    "                    ans = max(ans, label[i+1][j+1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "        m, n = len(A), len(B)\n",
    "        f = np.zeros(shape=(m+1, n+1), dtype=int)\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if A[i] == B[j]:\n",
    "                    f[i, j] = f[i+1, j+1] + 1\n",
    "        return f.max()\n",
    "        \n",
    "        \n",
    "        \n",
    "# class Solution(object):\n",
    "#     def findLength(self, A, B):\n",
    "#         memo = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]\n",
    "#         for i in range(len(A) - 1, -1, -1):\n",
    "#             for j in range(len(B) - 1, -1, -1):\n",
    "#                 if A[i] == B[j]:\n",
    "#                     memo[i][j] = memo[i+1][j+1]+1\n",
    "#         return max(max(row) for row in memo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "        lengthA = len(A)\n",
    "        lengthB = len(B)\n",
    "\n",
    "        if lengthA==0 or lengthB==0:\n",
    "            return 0\n",
    "\n",
    "        # ans = 0 \n",
    "        rst = np.zeros((lengthA+1, lengthB+1), dtype=int)\n",
    "        for i in range(1, lengthA+1):\n",
    "            for j in range(1, lengthB+1):\n",
    "                if A[i-1] == B[j-1]:\n",
    "                    rst[i,j] = rst[i-1,j-1] + 1\n",
    "                    # ans = max(rst[i,j], ans)\n",
    "                \n",
    "        return np.max(rst)\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "        n_A = len(A)\n",
    "        n_B = len(B)\n",
    "        dp = np.zeros((n_A+1, n_B+1))\n",
    "        for i in range(1, n_A+1):\n",
    "            for j in range(1, n_B+1):\n",
    "                if A[i-1] == B[j-1]:\n",
    "                    dp[i, j] = dp[i-1, j-1]+1\n",
    "                else:\n",
    "                    dp[i, j] = 0\n",
    "        return int(np.max(dp))\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np \n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "        n,m = len(A),len(B)\n",
    "\n",
    "        dp = np.full((n+1,m+1),0) #三维数组，分别是，数组1，数组2，是否相等\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m++1):\n",
    "                ia = i - 1\n",
    "                ib = j - 1\n",
    "\n",
    "                if(A[ia] == B[ib]):\n",
    "                    if  A[ia-1] == B[ib-1]:\n",
    "                        dp[i][j] = dp[i-1][j-1]+1\n",
    "                    else:\n",
    "                         dp[i][j]  = 1\n",
    "        return int(np.max(dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "        if not len(A) or not len(B):\n",
    "            return 0\n",
    "\n",
    "        dp = [[0] * (len(A) + 1) for _ in range(len(B) + 1)]\n",
    "\n",
    "        ans = 0\n",
    "        for j in range(len(B)-1, -1, -1):\n",
    "            for i in range(len(A)-1, -1, -1):\n",
    "                if A[i] == B[j]:\n",
    "                    dp[j][i] = dp[j + 1][i + 1] + 1\n",
    "                else:\n",
    "                    dp[j][i] = 0\n",
    "                ans = max(ans, dp[j][i])\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "        m=len(A)+1\n",
    "        n=len(B)+1\n",
    "        #dp=[[0]*n for i in range(m)]\n",
    "        import numpy\n",
    "        dp=numpy.zeros([m,n])\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if A[i-1]==B[j-1]:\n",
    "                    dp[i][j]=int(dp[i-1][j-1])+1\n",
    "        return int(numpy.max(dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        #获取两个数组的长度\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        #设置数组dp存放nums1和nums2最长的公共的数组，dp[i][j]表示nums1的前i个元素和nums2的前j个元素最长的公共数组长度\n",
    "        dp = [[0]*(n+1) for i in range(m+1)]\n",
    "        #初始化公共数组长度\n",
    "        ml = 0\n",
    "        #遍历所有元素,即nums1从1到第m个元素，nums2从1到第n个元素\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if nums1[i-1] == nums2[j-1]:         #nums1[i-1]表示nums1的第i个元素，nums2[j-1]表示nums2的第j个元素\n",
    "                    dp[i][j] = dp[i-1][j-1] +1     #dp[i][j]等于ums1的前i-1个元素和nums2的前j-1个元素最长的公共数组长度+1\n",
    "                    #更新公共数组长度\n",
    "                    ml = max(ml,dp[i][j])\n",
    "        #返回ml\n",
    "        return ml"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # dp[i][j]：以A[i-1]和B[j-1]结尾的数组最长重复子数组\n",
    "        # dp[i][j] = dp[i-1][j-1] + 1 若A[i-1]和B[j-1]相等\n",
    "        n1,n2 = len(nums1),len(nums2)\n",
    "        dp = [[0]*(n2+1) for _ in range(n1+1)]\n",
    "        ans = 0\n",
    "        for i in range(1,n1+1):\n",
    "            for j in range(1,n2+1):\n",
    "                if nums1[i-1]==nums2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+1\n",
    "            ans = max(ans,max(dp[i]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dp = [[0]*(len(nums2)+1) for _ in range(len(nums1)+1)]\n",
    "        result = 0\n",
    "        for i in range(1,len(nums1)+1):\n",
    "            for j in range(1,len(nums2)+1):\n",
    "                if nums1[i-1] == nums2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+1\n",
    "                    result = max(dp[i][j],result)\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 创建一个二维数组 dp，用于存储最长公共子数组的长度\n",
    "        dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]\n",
    "        # 记录最长公共子数组的长度\n",
    "        result = 0\n",
    "\n",
    "        # 遍历数组 nums1\n",
    "        for i in range(1, len(nums1) + 1):\n",
    "            # 遍历数组 nums2\n",
    "            for j in range(1, len(nums2) + 1):\n",
    "                # 如果 nums1[i-1] 和 nums2[j-1] 相等\n",
    "                if nums1[i - 1] == nums2[j - 1]:\n",
    "                    # 在当前位置上的最长公共子数组长度为前一个位置上的长度加一\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                # 更新最长公共子数组的长度\n",
    "                if dp[i][j] > result:\n",
    "                    result = dp[i][j]\n",
    "\n",
    "        # 返回最长公共子数组的长度\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, A: List[int], B: List[int]) -> int:\n",
    "        dp = [[0]*(len(B)+1) for _ in range(len(A)+1)]\n",
    "\n",
    "        res = 0 \n",
    "        for i in range(1,len(A)+1):\n",
    "            for j in range(1,len(B)+1):\n",
    "                if A[i-1] == B[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                res = max(res,dp[i][j])\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m,n=len(nums1),len(nums2)\n",
    "        ans=0\n",
    "        dp=[[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if nums1[i-1] == nums2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+1\n",
    "                    ans =max(ans,dp[i][j])\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
